This notebook is all about benchmarking some R code used in this package.

Hardware / Software used:

  • Intel i7-4600U
  • Compilation flags for C/C++: -O2 -Wall $(DEBUGFLAG) -mtune=core2 (R’s defaults)
  • Windows Server 2012 R2
  • R 3.3.2 + Intel MKL

Libraries

library(data.table)
data.table 1.10.4
  The fastest way to learn (by data.table authors): https://www.datacamp.com/courses/data-analysis-the-data-table-way
  Documentation: ?data.table, example(data.table) and browseVignettes("data.table")
  Release notes, videos and slides: http://r-datatable.com
library(microbenchmark)
library(Rcpp)
library(ggplot2)
library(plotly)

Attaching package: <U+393C><U+3E31>plotly<U+393C><U+3E32>

The following object is masked from <U+393C><U+3E31>package:ggplot2<U+393C><U+3E32>:

    last_plot

The following object is masked from <U+393C><U+3E31>package:stats<U+393C><U+3E32>:

    filter

The following object is masked from <U+393C><U+3E31>package:graphics<U+393C><U+3E32>:

    layout
# Helper function to print data well in tables
print_well <- function(data, digits = 6) {
  
  # To milliseconds
  data <- data / 1000000
  
  # Sprintf helper
  sprintf_helper <- paste0("%.0", digits, "f")
  
  cat("| Min | 25% | 50% | 75% | Max | Mean |  \n| --: | --: | --: | --: | --: | --: |  \n| ", sprintf(sprintf_helper, min(data)), " | ", sprintf(sprintf_helper, quantile(data, probs = 0.25)), " | ", sprintf(sprintf_helper, median(data)), " | ", sprintf(sprintf_helper, quantile(data, probs = 0.75)), " | ", sprintf(sprintf_helper, max(data)), " | ", sprintf(sprintf_helper, mean(data)), " |  \n", sep = "")
  
  return(data)
  
}
# Test case function
# Arguments renamed to avoid recursive clash
test_case <- function(f, preds, labels, eps) {
  cat("Test case: ", paste(do.call(f, list(preds = preds[1:50],
                                           labels = labels[1:5],
                                           eps = 1e-15)), collapse = ", "), "  \n")
}
# Fastest Logloss function
cppFunction("double Lpp_logloss1(NumericVector preds, NumericVector labels, double eps) {
  NumericVector clamped = clamp(eps, preds, 1 - eps);
  NumericVector loggy = -log(1 - clamped);
  double logloss = sum(loggy) / loggy.size();
  return logloss;
}")
# Fastest Transformer function
cppFunction("NumericVector Lpp_vec2mat2vec(NumericVector preds, NumericVector labels) {
  int labels_size = labels.size();
  NumericVector selected(labels_size);
  selected = (preds.size() / labels_size) * seq(0, labels_size - 1);
  selected = selected + labels;
  NumericVector to_return(labels_size);
  to_return = preds[selected];
  return to_return;
}")

Benchmarking Clamped Vector to Logloss

For a 10-class vector of 1,000,000 observations:

  • Vector A of length=(1000000 * 10)
  • Vector B of length=(1000000) with 10 classes
A = [1:1, 1:2, 1:3, 1:4... 1:10, 2:1, 2:2, 2:3..., 1000000:8, 1000000:9, 1000000:10]
B = [3, 5, 9, 1, 4, 8, 6, ...]

Get the following Vector C, D, and E:

C = [1:4, 2:6, 3:10, 4:2, 5:5, 6:9, 7:7, ...]
D = Clamped C by 1e-15
E = Mean of logloss(D, B)

Initialize data

# Generate random data
set.seed(11111)
data <- runif(10000000, 0, 1)
labels <- round(runif(1000000, 0, 9), digits = 0)
# Background truth example (no clamping though)
array(data[1:50], dim = c(10, 5))
           [,1]       [,2]       [,3]       [,4]       [,5]
 [1,] 0.5014483 0.57219649 0.70236924 0.06440384 0.78924978
 [2,] 0.9702328 0.34292525 0.50889166 0.65780657 0.72449914
 [3,] 0.7876004 0.09627503 0.20268701 0.19973930 0.00886554
 [4,] 0.9022259 0.74235690 0.90706612 0.24664551 0.57348710
 [5,] 0.8141778 0.42274539 0.05441064 0.25997440 0.73034459
 [6,] 0.7998922 0.98402494 0.09045308 0.14869691 0.42458612
 [7,] 0.1158690 0.89258437 0.85759800 0.21375685 0.07684022
 [8,] 0.7171363 0.59541565 0.94780036 0.20598170 0.53318628
 [9,] 0.1020639 0.80531234 0.16479666 0.02075780 0.28521238
[10,] 0.6856938 0.42102379 0.42536097 0.63880218 0.86408083
labels[1:5]
[1] 5 1 1 7 8
data[c(1 + labels[1], 11 + labels[2], 21 + labels[3], 31 + labels[4], 41 + labels[5])]
[1] 0.7998922 0.3429253 0.5088917 0.2059817 0.2852124
-log(1 - data[c(1 + labels[1], 11 + labels[2], 21 + labels[3], 31 + labels[4], 41 + labels[5])])
[1] 1.6088991 0.4199575 0.7110905 0.2306488 0.3357698
mean(-log(1 - data[c(1 + labels[1], 11 + labels[2], 21 + labels[3], 31 + labels[4], 41 + labels[5])]))
[1] 0.6612731
# How many digits for benchmarking in milliseconds
my_digits <- 6L
# How many runs for benchmarking?
my_runs <- 1000L

Benchmarks

# ===== BLOCK 1 =====
faster1 <- function(preds, labels, eps = 1e-15) {
  temp_preds <- Lpp_vec2mat2vec(preds, labels)
  temp_log <- Lpp_logloss1(temp_preds, labels, eps)
  return(temp_log)
}
test_case(faster1, preds = data, labels = labels, eps = 1e-15)

Test case: 0.661273148685013

data1 <- print_well(microbenchmark(faster1(data, labels), times = my_runs)$time, digits = my_digits)
Min 25% 50% 75% Max Mean
68.926756 74.804619 78.212735 81.261905 164.202304 80.309716
# ===== BLOCK 2 =====
faster2 <- function(preds, labels, eps = 1e-15) {
  x <- pmin(pmax(preds[((0:(length(labels) - 1)) * (length(preds) / length(labels))) + labels + 1], eps), 1 - eps)
  return(-mean(log(1 - x)))
}
test_case(faster2, preds = data, labels = labels, eps = 1e-15)

Test case: 0.661273148685013

data2 <- print_well(microbenchmark(faster2(data, labels), times = my_runs)$time, digits = my_digits)
Min 25% 50% 75% Max Mean
77.518225 83.980548 87.441692 92.275130 184.003622 93.454641
# ===== BLOCK 3 =====
faster3 <- function(preds, labels, eps = 1e-15) {
  x <- pmin(pmax(preds[((0:(length(labels) - 1)) * (length(preds) / length(labels))) + labels + 1], eps), 1 - eps)
  return(-sum(log(1 - x)) / length(labels))
}
test_case(faster3, preds = data, labels = labels, eps = 1e-15)

Test case: 0.661273148685013

data3 <- print_well(microbenchmark(faster3(data, labels), times = my_runs)$time, digits = my_digits)
Min 25% 50% 75% Max Mean
77.040393 83.824502 86.537727 89.636696 178.287507 90.702964
# ===== BLOCK 4 =====
cppFunction("double faster4(NumericVector preds, NumericVector labels, double eps) {
  int labels_size = labels.size();
  NumericVector selected(labels_size);
  selected = (preds.size() / labels_size) * seq(0, labels_size - 1);
  selected = selected + labels;
  NumericVector to_return(labels_size);
  to_return = preds[selected];
  NumericVector clamped = clamp(eps, to_return, 1 - eps);
  NumericVector loggy = -(log(1 - clamped));
  double logloss = sum(loggy) / labels_size;
  return logloss;
}")
test_case(faster4, preds = data, labels = labels, eps = 1e-15)

Test case: 0.661273148685013

data4 <- print_well(microbenchmark(faster4(data, labels, eps = 1e-15), times = my_runs)$time, digits = my_digits)
Min 25% 50% 75% Max Mean
68.495682 70.417652 79.347062 80.943635 149.402824 77.465465

Summary Results

data_time <- data.table(rbindlist(list(data.frame(Time = data1, Bench = "faster1"),
                                       data.frame(Time = data2, Bench = "faster2"),
                                       data.frame(Time = data3, Bench = "faster3"),
                                       data.frame(Time = data4, Bench = "faster4"))))
data_time <- data_time[, t_mean := mean(Time), by = Bench]
data_time <- data_time[, t_median := median(Time), by = Bench]
data_time$Benchs <- data_time$Bench 
levels(data_time$Benchs) <- paste0("faster", 1:4, "= [", sprintf(paste0("%.0", my_digits, "f"), data_time[, list(min(Time)), by = Bench]$V1), ", ", sprintf(paste0("%.0", my_digits, "f"), data_time[, list(max(Time)), by = Bench]$V1), "], mean=", sprintf(paste0("%.0", my_digits, "f"), data_time[, list(mean(Time)), by = Bench]$V1), ", median=", sprintf(paste0("%.0", my_digits, "f"), data_time[, list(median(Time)), by = Bench]$V1))
my_time <- data_time[, list(min(Time), quantile(Time, probs = 0.25), median(Time), quantile(Time, probs = 0.75), max(Time), mean(Time)), by = Bench]
colnames(my_time) <- c("Function", "Min", "25%", "50%", "75%", "Max", "Mean")
my_time <- my_time[order(Mean, decreasing = FALSE), ]
print(my_time, digits = 6)

Plot Results

ggplotly(ggplot(data = data_time, aes(x = Time)) + geom_histogram(aes(y = ..density..), bins = 20, color = "darkblue", fill = "lightblue") + facet_wrap(~ Benchs, ncol = 2) + geom_vline(aes(xintercept = t_mean), color = "blue", linetype = "dashed", size = 2) + geom_vline(aes(xintercept = t_median), color = "red", linetype = "dashed", size = 2) + labs(x = "Time (Milliseconds)", y = "Density") + theme_bw())
ggplotly(ggplot(data = data_time[, .(Time, Bench)], aes(x = Time, y = ..count.., fill = Bench)) + geom_histogram(aes(y = ..density..), bins = 100, position = "fill") + labs(x = "Time (Milliseconds)", y = "Density") + theme_bw())
ggplotly(ggplot(data = data_time[, .(Time, Bench)], aes(x = Time, y = ..count.., fill = Bench)) + geom_density(position = "fill") + labs(x = "Time (Milliseconds)", y = "Density") + theme_bw())
LS0tDQp0aXRsZTogIkJlbmNobWFya3M6IE11bHRpLWNsYXNzIExvZ2xvc3MiDQpvdXRwdXQ6DQogIGh0bWxfbm90ZWJvb2s6DQogICAgY29sbGFwc2VkOiBubw0KICAgIHRoZW1lOiB1bml0ZWQNCiAgICB0b2M6IHllcw0KICAgIHRvY19kZXB0aDogNg0KICAgIHRvY19mbG9hdDogeWVzDQoNCi0tLQ0KDQpUaGlzIG5vdGVib29rIGlzIGFsbCBhYm91dCBiZW5jaG1hcmtpbmcgc29tZSBSIGNvZGUgdXNlZCBpbiB0aGlzIHBhY2thZ2UuDQoNCkhhcmR3YXJlIC8gU29mdHdhcmUgdXNlZDoNCg0KKiBJbnRlbCBpNy00NjAwVQ0KKiBDb21waWxhdGlvbiBmbGFncyBmb3IgQy9DKys6IGAtTzIgLVdhbGwgJChERUJVR0ZMQUcpIC1tdHVuZT1jb3JlMmAgKFIncyBkZWZhdWx0cykNCiogV2luZG93cyBTZXJ2ZXIgMjAxMiBSMg0KKiBSIDMuMy4yICsgSW50ZWwgTUtMDQoNCiMgTGlicmFyaWVzDQoNCmBgYHtyIGluaXR9DQpsaWJyYXJ5KGRhdGEudGFibGUpDQpsaWJyYXJ5KG1pY3JvYmVuY2htYXJrKQ0KbGlicmFyeShSY3BwKQ0KbGlicmFyeShnZ3Bsb3QyKQ0KbGlicmFyeShwbG90bHkpDQpgYGANCg0KYGBge3IgYmFzZWR9DQoNCiMgSGVscGVyIGZ1bmN0aW9uIHRvIHByaW50IGRhdGEgd2VsbCBpbiB0YWJsZXMNCnByaW50X3dlbGwgPC0gZnVuY3Rpb24oZGF0YSwgZGlnaXRzID0gNikgew0KICANCiAgIyBUbyBtaWxsaXNlY29uZHMNCiAgZGF0YSA8LSBkYXRhIC8gMTAwMDAwMA0KICANCiAgIyBTcHJpbnRmIGhlbHBlcg0KICBzcHJpbnRmX2hlbHBlciA8LSBwYXN0ZTAoIiUuMCIsIGRpZ2l0cywgImYiKQ0KICANCiAgY2F0KCJ8IE1pbiB8IDI1JSB8IDUwJSB8IDc1JSB8IE1heCB8IE1lYW4gfCAgXG58IC0tOiB8IC0tOiB8IC0tOiB8IC0tOiB8IC0tOiB8IC0tOiB8ICBcbnwgIiwgc3ByaW50ZihzcHJpbnRmX2hlbHBlciwgbWluKGRhdGEpKSwgIiB8ICIsIHNwcmludGYoc3ByaW50Zl9oZWxwZXIsIHF1YW50aWxlKGRhdGEsIHByb2JzID0gMC4yNSkpLCAiIHwgIiwgc3ByaW50ZihzcHJpbnRmX2hlbHBlciwgbWVkaWFuKGRhdGEpKSwgIiB8ICIsIHNwcmludGYoc3ByaW50Zl9oZWxwZXIsIHF1YW50aWxlKGRhdGEsIHByb2JzID0gMC43NSkpLCAiIHwgIiwgc3ByaW50ZihzcHJpbnRmX2hlbHBlciwgbWF4KGRhdGEpKSwgIiB8ICIsIHNwcmludGYoc3ByaW50Zl9oZWxwZXIsIG1lYW4oZGF0YSkpLCAiIHwgIFxuIiwgc2VwID0gIiIpDQogIA0KICByZXR1cm4oZGF0YSkNCiAgDQp9DQoNCiMgVGVzdCBjYXNlIGZ1bmN0aW9uDQojIEFyZ3VtZW50cyByZW5hbWVkIHRvIGF2b2lkIHJlY3Vyc2l2ZSBjbGFzaA0KdGVzdF9jYXNlIDwtIGZ1bmN0aW9uKGYsIHByZWRzLCBsYWJlbHMsIGVwcykgew0KICBjYXQoIlRlc3QgY2FzZTogIiwgcGFzdGUoZG8uY2FsbChmLCBsaXN0KHByZWRzID0gcHJlZHNbMTo1MF0sDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbGFiZWxzID0gbGFiZWxzWzE6NV0sDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZXBzID0gMWUtMTUpKSwgY29sbGFwc2UgPSAiLCAiKSwgIiAgXG4iKQ0KfQ0KDQojIEZhc3Rlc3QgTG9nbG9zcyBmdW5jdGlvbg0KY3BwRnVuY3Rpb24oImRvdWJsZSBMcHBfbG9nbG9zczEoTnVtZXJpY1ZlY3RvciBwcmVkcywgTnVtZXJpY1ZlY3RvciBsYWJlbHMsIGRvdWJsZSBlcHMpIHsNCiAgTnVtZXJpY1ZlY3RvciBjbGFtcGVkID0gY2xhbXAoZXBzLCBwcmVkcywgMSAtIGVwcyk7DQogIE51bWVyaWNWZWN0b3IgbG9nZ3kgPSAtbG9nKDEgLSBjbGFtcGVkKTsNCiAgZG91YmxlIGxvZ2xvc3MgPSBzdW0obG9nZ3kpIC8gbG9nZ3kuc2l6ZSgpOw0KICByZXR1cm4gbG9nbG9zczsNCn0iKQ0KDQojIEZhc3Rlc3QgVHJhbnNmb3JtZXIgZnVuY3Rpb24NCmNwcEZ1bmN0aW9uKCJOdW1lcmljVmVjdG9yIExwcF92ZWMybWF0MnZlYyhOdW1lcmljVmVjdG9yIHByZWRzLCBOdW1lcmljVmVjdG9yIGxhYmVscykgew0KICBpbnQgbGFiZWxzX3NpemUgPSBsYWJlbHMuc2l6ZSgpOw0KICBOdW1lcmljVmVjdG9yIHNlbGVjdGVkKGxhYmVsc19zaXplKTsNCiAgc2VsZWN0ZWQgPSAocHJlZHMuc2l6ZSgpIC8gbGFiZWxzX3NpemUpICogc2VxKDAsIGxhYmVsc19zaXplIC0gMSk7DQogIHNlbGVjdGVkID0gc2VsZWN0ZWQgKyBsYWJlbHM7DQogIE51bWVyaWNWZWN0b3IgdG9fcmV0dXJuKGxhYmVsc19zaXplKTsNCiAgdG9fcmV0dXJuID0gcHJlZHNbc2VsZWN0ZWRdOw0KICByZXR1cm4gdG9fcmV0dXJuOw0KfSIpDQoNCmBgYA0KDQojIEJlbmNobWFya2luZyBDbGFtcGVkIFZlY3RvciB0byBMb2dsb3NzDQoNCkZvciBhIDEwLWNsYXNzIHZlY3RvciBvZiAxLDAwMCwwMDAgb2JzZXJ2YXRpb25zOg0KDQoqIFZlY3RvciBBIG9mIGxlbmd0aD0oMTAwMDAwMCAqIDEwKQ0KKiBWZWN0b3IgQiBvZiBsZW5ndGg9KDEwMDAwMDApIHdpdGggMTAgY2xhc3Nlcw0KDQpgYGANCkEgPSBbMToxLCAxOjIsIDE6MywgMTo0Li4uIDE6MTAsIDI6MSwgMjoyLCAyOjMuLi4sIDEwMDAwMDA6OCwgMTAwMDAwMDo5LCAxMDAwMDAwOjEwXQ0KQiA9IFszLCA1LCA5LCAxLCA0LCA4LCA2LCAuLi5dDQpgYGANCg0KR2V0IHRoZSBmb2xsb3dpbmcgVmVjdG9yIEMsIEQsIGFuZCBFOg0KDQpgYGANCkMgPSBbMTo0LCAyOjYsIDM6MTAsIDQ6MiwgNTo1LCA2OjksIDc6NywgLi4uXQ0KRCA9IENsYW1wZWQgQyBieSAxZS0xNQ0KRSA9IE1lYW4gb2YgbG9nbG9zcyhELCBCKQ0KYGBgDQoNCiMgSW5pdGlhbGl6ZSBkYXRhDQoNCmBgYHtyIGJlbmNoMX0NCiMgR2VuZXJhdGUgcmFuZG9tIGRhdGENCnNldC5zZWVkKDExMTExKQ0KZGF0YSA8LSBydW5pZigxMDAwMDAwMCwgMCwgMSkNCmxhYmVscyA8LSByb3VuZChydW5pZigxMDAwMDAwLCAwLCA5KSwgZGlnaXRzID0gMCkNCg0KIyBCYWNrZ3JvdW5kIHRydXRoIGV4YW1wbGUgKG5vIGNsYW1waW5nIHRob3VnaCkNCmFycmF5KGRhdGFbMTo1MF0sIGRpbSA9IGMoMTAsIDUpKQ0KbGFiZWxzWzE6NV0NCmRhdGFbYygxICsgbGFiZWxzWzFdLCAxMSArIGxhYmVsc1syXSwgMjEgKyBsYWJlbHNbM10sIDMxICsgbGFiZWxzWzRdLCA0MSArIGxhYmVsc1s1XSldDQotbG9nKDEgLSBkYXRhW2MoMSArIGxhYmVsc1sxXSwgMTEgKyBsYWJlbHNbMl0sIDIxICsgbGFiZWxzWzNdLCAzMSArIGxhYmVsc1s0XSwgNDEgKyBsYWJlbHNbNV0pXSkNCm1lYW4oLWxvZygxIC0gZGF0YVtjKDEgKyBsYWJlbHNbMV0sIDExICsgbGFiZWxzWzJdLCAyMSArIGxhYmVsc1szXSwgMzEgKyBsYWJlbHNbNF0sIDQxICsgbGFiZWxzWzVdKV0pKQ0KDQojIEhvdyBtYW55IGRpZ2l0cyBmb3IgYmVuY2htYXJraW5nIGluIG1pbGxpc2Vjb25kcw0KbXlfZGlnaXRzIDwtIDZMDQoNCiMgSG93IG1hbnkgcnVucyBmb3IgYmVuY2htYXJraW5nPw0KbXlfcnVucyA8LSAxMDAwTA0KYGBgDQoNCiMgQmVuY2htYXJrcw0KDQpgYGB7ciBiZW5jaDIsIHJlc3VsdHM9ImFzaXMifQ0KDQojID09PT09IEJMT0NLIDEgPT09PT0NCmZhc3RlcjEgPC0gZnVuY3Rpb24ocHJlZHMsIGxhYmVscywgZXBzID0gMWUtMTUpIHsNCiAgdGVtcF9wcmVkcyA8LSBMcHBfdmVjMm1hdDJ2ZWMocHJlZHMsIGxhYmVscykNCiAgdGVtcF9sb2cgPC0gTHBwX2xvZ2xvc3MxKHRlbXBfcHJlZHMsIGxhYmVscywgZXBzKQ0KICByZXR1cm4odGVtcF9sb2cpDQp9DQp0ZXN0X2Nhc2UoZmFzdGVyMSwgcHJlZHMgPSBkYXRhLCBsYWJlbHMgPSBsYWJlbHMsIGVwcyA9IDFlLTE1KQ0KZGF0YTEgPC0gcHJpbnRfd2VsbChtaWNyb2JlbmNobWFyayhmYXN0ZXIxKGRhdGEsIGxhYmVscyksIHRpbWVzID0gbXlfcnVucykkdGltZSwgZGlnaXRzID0gbXlfZGlnaXRzKQ0KDQojID09PT09IEJMT0NLIDIgPT09PT0NCmZhc3RlcjIgPC0gZnVuY3Rpb24ocHJlZHMsIGxhYmVscywgZXBzID0gMWUtMTUpIHsNCiAgeCA8LSBwbWluKHBtYXgocHJlZHNbKCgwOihsZW5ndGgobGFiZWxzKSAtIDEpKSAqIChsZW5ndGgocHJlZHMpIC8gbGVuZ3RoKGxhYmVscykpKSArIGxhYmVscyArIDFdLCBlcHMpLCAxIC0gZXBzKQ0KICByZXR1cm4oLW1lYW4obG9nKDEgLSB4KSkpDQp9DQp0ZXN0X2Nhc2UoZmFzdGVyMiwgcHJlZHMgPSBkYXRhLCBsYWJlbHMgPSBsYWJlbHMsIGVwcyA9IDFlLTE1KQ0KZGF0YTIgPC0gcHJpbnRfd2VsbChtaWNyb2JlbmNobWFyayhmYXN0ZXIyKGRhdGEsIGxhYmVscyksIHRpbWVzID0gbXlfcnVucykkdGltZSwgZGlnaXRzID0gbXlfZGlnaXRzKQ0KDQojID09PT09IEJMT0NLIDMgPT09PT0NCmZhc3RlcjMgPC0gZnVuY3Rpb24ocHJlZHMsIGxhYmVscywgZXBzID0gMWUtMTUpIHsNCiAgeCA8LSBwbWluKHBtYXgocHJlZHNbKCgwOihsZW5ndGgobGFiZWxzKSAtIDEpKSAqIChsZW5ndGgocHJlZHMpIC8gbGVuZ3RoKGxhYmVscykpKSArIGxhYmVscyArIDFdLCBlcHMpLCAxIC0gZXBzKQ0KICByZXR1cm4oLXN1bShsb2coMSAtIHgpKSAvIGxlbmd0aChsYWJlbHMpKQ0KfQ0KdGVzdF9jYXNlKGZhc3RlcjMsIHByZWRzID0gZGF0YSwgbGFiZWxzID0gbGFiZWxzLCBlcHMgPSAxZS0xNSkNCmRhdGEzIDwtIHByaW50X3dlbGwobWljcm9iZW5jaG1hcmsoZmFzdGVyMyhkYXRhLCBsYWJlbHMpLCB0aW1lcyA9IG15X3J1bnMpJHRpbWUsIGRpZ2l0cyA9IG15X2RpZ2l0cykNCg0KIyA9PT09PSBCTE9DSyA0ID09PT09DQpjcHBGdW5jdGlvbigiZG91YmxlIGZhc3RlcjQoTnVtZXJpY1ZlY3RvciBwcmVkcywgTnVtZXJpY1ZlY3RvciBsYWJlbHMsIGRvdWJsZSBlcHMpIHsNCiAgaW50IGxhYmVsc19zaXplID0gbGFiZWxzLnNpemUoKTsNCiAgTnVtZXJpY1ZlY3RvciBzZWxlY3RlZChsYWJlbHNfc2l6ZSk7DQogIHNlbGVjdGVkID0gKHByZWRzLnNpemUoKSAvIGxhYmVsc19zaXplKSAqIHNlcSgwLCBsYWJlbHNfc2l6ZSAtIDEpOw0KICBzZWxlY3RlZCA9IHNlbGVjdGVkICsgbGFiZWxzOw0KICBOdW1lcmljVmVjdG9yIHRvX3JldHVybihsYWJlbHNfc2l6ZSk7DQogIHRvX3JldHVybiA9IHByZWRzW3NlbGVjdGVkXTsNCiAgTnVtZXJpY1ZlY3RvciBjbGFtcGVkID0gY2xhbXAoZXBzLCB0b19yZXR1cm4sIDEgLSBlcHMpOw0KICBOdW1lcmljVmVjdG9yIGxvZ2d5ID0gLShsb2coMSAtIGNsYW1wZWQpKTsNCiAgZG91YmxlIGxvZ2xvc3MgPSBzdW0obG9nZ3kpIC8gbGFiZWxzX3NpemU7DQogIHJldHVybiBsb2dsb3NzOw0KfSIpDQp0ZXN0X2Nhc2UoZmFzdGVyNCwgcHJlZHMgPSBkYXRhLCBsYWJlbHMgPSBsYWJlbHMsIGVwcyA9IDFlLTE1KQ0KZGF0YTQgPC0gcHJpbnRfd2VsbChtaWNyb2JlbmNobWFyayhmYXN0ZXI0KGRhdGEsIGxhYmVscywgZXBzID0gMWUtMTUpLCB0aW1lcyA9IG15X3J1bnMpJHRpbWUsIGRpZ2l0cyA9IG15X2RpZ2l0cykNCg0KYGBgDQoNCiMgU3VtbWFyeSBSZXN1bHRzDQoNCmBgYHtyIGJlbmNoM30NCg0KZGF0YV90aW1lIDwtIGRhdGEudGFibGUocmJpbmRsaXN0KGxpc3QoZGF0YS5mcmFtZShUaW1lID0gZGF0YTEsIEJlbmNoID0gImZhc3RlcjEiKSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRhdGEuZnJhbWUoVGltZSA9IGRhdGEyLCBCZW5jaCA9ICJmYXN0ZXIyIiksDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkYXRhLmZyYW1lKFRpbWUgPSBkYXRhMywgQmVuY2ggPSAiZmFzdGVyMyIpLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGF0YS5mcmFtZShUaW1lID0gZGF0YTQsIEJlbmNoID0gImZhc3RlcjQiKSkpKQ0KZGF0YV90aW1lIDwtIGRhdGFfdGltZVssIHRfbWVhbiA6PSBtZWFuKFRpbWUpLCBieSA9IEJlbmNoXQ0KZGF0YV90aW1lIDwtIGRhdGFfdGltZVssIHRfbWVkaWFuIDo9IG1lZGlhbihUaW1lKSwgYnkgPSBCZW5jaF0NCmRhdGFfdGltZSRCZW5jaHMgPC0gZGF0YV90aW1lJEJlbmNoIA0KbGV2ZWxzKGRhdGFfdGltZSRCZW5jaHMpIDwtIHBhc3RlMCgiZmFzdGVyIiwgMTo0LCAiPSBbIiwgc3ByaW50ZihwYXN0ZTAoIiUuMCIsIG15X2RpZ2l0cywgImYiKSwgZGF0YV90aW1lWywgbGlzdChtaW4oVGltZSkpLCBieSA9IEJlbmNoXSRWMSksICIsICIsIHNwcmludGYocGFzdGUwKCIlLjAiLCBteV9kaWdpdHMsICJmIiksIGRhdGFfdGltZVssIGxpc3QobWF4KFRpbWUpKSwgYnkgPSBCZW5jaF0kVjEpLCAiXSwgbWVhbj0iLCBzcHJpbnRmKHBhc3RlMCgiJS4wIiwgbXlfZGlnaXRzLCAiZiIpLCBkYXRhX3RpbWVbLCBsaXN0KG1lYW4oVGltZSkpLCBieSA9IEJlbmNoXSRWMSksICIsIG1lZGlhbj0iLCBzcHJpbnRmKHBhc3RlMCgiJS4wIiwgbXlfZGlnaXRzLCAiZiIpLCBkYXRhX3RpbWVbLCBsaXN0KG1lZGlhbihUaW1lKSksIGJ5ID0gQmVuY2hdJFYxKSkNCg0KbXlfdGltZSA8LSBkYXRhX3RpbWVbLCBsaXN0KG1pbihUaW1lKSwgcXVhbnRpbGUoVGltZSwgcHJvYnMgPSAwLjI1KSwgbWVkaWFuKFRpbWUpLCBxdWFudGlsZShUaW1lLCBwcm9icyA9IDAuNzUpLCBtYXgoVGltZSksIG1lYW4oVGltZSkpLCBieSA9IEJlbmNoXQ0KY29sbmFtZXMobXlfdGltZSkgPC0gYygiRnVuY3Rpb24iLCAiTWluIiwgIjI1JSIsICI1MCUiLCAiNzUlIiwgIk1heCIsICJNZWFuIikNCm15X3RpbWUgPC0gbXlfdGltZVtvcmRlcihNZWFuLCBkZWNyZWFzaW5nID0gRkFMU0UpLCBdDQpwcmludChteV90aW1lLCBkaWdpdHMgPSA2KQ0KDQpgYGANCg0KIyBQbG90IFJlc3VsdHMNCg0KYGBge3IgYmVuY2g0LCBmaWcuaGVpZ2h0PTYsIGZpZy53aWR0aD0xMH0NCg0KZ2dwbG90bHkoZ2dwbG90KGRhdGEgPSBkYXRhX3RpbWUsIGFlcyh4ID0gVGltZSkpICsgZ2VvbV9oaXN0b2dyYW0oYWVzKHkgPSAuLmRlbnNpdHkuLiksIGJpbnMgPSAyMCwgY29sb3IgPSAiZGFya2JsdWUiLCBmaWxsID0gImxpZ2h0Ymx1ZSIpICsgZmFjZXRfd3JhcCh+IEJlbmNocywgbmNvbCA9IDIpICsgZ2VvbV92bGluZShhZXMoeGludGVyY2VwdCA9IHRfbWVhbiksIGNvbG9yID0gImJsdWUiLCBsaW5ldHlwZSA9ICJkYXNoZWQiLCBzaXplID0gMikgKyBnZW9tX3ZsaW5lKGFlcyh4aW50ZXJjZXB0ID0gdF9tZWRpYW4pLCBjb2xvciA9ICJyZWQiLCBsaW5ldHlwZSA9ICJkYXNoZWQiLCBzaXplID0gMikgKyBsYWJzKHggPSAiVGltZSAoTWlsbGlzZWNvbmRzKSIsIHkgPSAiRGVuc2l0eSIpICsgdGhlbWVfYncoKSkNCg0KYGBgDQoNCmBgYHtyIGJlbmNoNSwgZmlnLmhlaWdodD02LCBmaWcud2lkdGg9MTB9DQpnZ3Bsb3RseShnZ3Bsb3QoZGF0YSA9IGRhdGFfdGltZVssIC4oVGltZSwgQmVuY2gpXSwgYWVzKHggPSBUaW1lLCB5ID0gLi5jb3VudC4uLCBmaWxsID0gQmVuY2gpKSArIGdlb21faGlzdG9ncmFtKGFlcyh5ID0gLi5kZW5zaXR5Li4pLCBiaW5zID0gMTAwLCBwb3NpdGlvbiA9ICJmaWxsIikgKyBsYWJzKHggPSAiVGltZSAoTWlsbGlzZWNvbmRzKSIsIHkgPSAiRGVuc2l0eSIpICsgdGhlbWVfYncoKSkNCmBgYA0KDQpgYGB7ciBiZW5jaDYsIGZpZy5oZWlnaHQ9NiwgZmlnLndpZHRoPTEwfQ0KZ2dwbG90bHkoZ2dwbG90KGRhdGEgPSBkYXRhX3RpbWVbLCAuKFRpbWUsIEJlbmNoKV0sIGFlcyh4ID0gVGltZSwgeSA9IC4uY291bnQuLiwgZmlsbCA9IEJlbmNoKSkgKyBnZW9tX2RlbnNpdHkocG9zaXRpb24gPSAiZmlsbCIpICsgbGFicyh4ID0gIlRpbWUgKE1pbGxpc2Vjb25kcykiLCB5ID0gIkRlbnNpdHkiKSArIHRoZW1lX2J3KCkpDQpgYGANCg0K